package com.zhouxianglh.p54;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵
 * 标记 L,D,R,U  对应 左,下,右,上 四个方向
 *
 * @author zhouxianglh
 */
public class Solution {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if (matrix.length == 0) {
            return list;
        }
        int startColumn = 0;
        int endColumn = matrix[0].length - 1;
        int startRow = 0;
        int endRow = matrix.length - 1;
        int row = 0;
        int column = 0;
        char direction = 'L';

        list.add(matrix[0][0]);
        while (true) {
            if (startColumn == endColumn && startRow == endRow && (startColumn != 0 || startRow != 0)) {
                list.add(matrix[endRow][startColumn]);
                return list;
            }
            if (startColumn > endColumn || startRow > endRow) {
                return list;
            }
            switch (direction) {
                case 'L':
                    if (column + 1 > endColumn) {
                        direction = 'D';
                        startRow++;
                        continue;
                    } else {
                        column++;
                    }
                    break;
                case 'D':
                    if (row + 1 > endRow) {
                        direction = 'R';
                        endColumn--;
                        continue;
                    } else {
                        row++;
                    }
                    break;
                case 'R':
                    if (column - 1 < startColumn) {
                        direction = 'U';
                        endRow--;
                        continue;
                    } else {
                        column--;
                    }
                    break;
                case 'U':
                    if (row - 1 < startRow) {
                        direction = 'L';
                        startColumn++;
                        continue;
                    } else {
                        row--;
                    }
                    break;
                default:
                    throw new RuntimeException();
            }
            list.add(matrix[row][column]);
        }
    }

    public static void main(String[] args) {
        int[][] intArr = new int[][]{{1, 2, 3}, {4, 5, 6}};
        System.out.println(spiralOrder(intArr));
        //
        intArr = new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12, 13}};
        System.out.println(spiralOrder(intArr));
        //
        intArr = new int[][]{};
        System.out.println(spiralOrder(intArr));
        //
        intArr = new int[][]{{3}, {2}};
        System.out.println(spiralOrder(intArr));
    }
}
